There Is No Preview Available For This Item
This item does not appear to have any files that can be experienced on Archive.org.
Please download files in this item to interact with them on your computer.
Show all files
The Markov Chain Monte Carlo method is arguably the most powerful algorithmic tool available for approximate counting problems. Most known algorithms for such problems follow the paradigm of defining a Markov chain and showing that it mixes rapidly. However, there are natural counting problems where the obvious Markov chains do not mix rapidly. Annealing and Simulated Tempering are two heuristic approaches that can be applied in such situations. Both aim at finding ways to circumvent bottlenecks that cause Markov chains to mix slowly. In this talk, we will explore the power and limitations of these approaches.
We present a simulated annealing based algorithm for the problem of generating random binary contingency tables. This problem can be restated as generating random bipartite graphs with a given degree sequence. This is based on joint work with Ivona Bezakova and Eric Vigoda. On the flip side, we show that in some scenarios, simulated tempering fails to speed up the mixing of the Markov chain and in fact no temperature based interpolants for the tempering algorithm can succeed. This is based on joint work with Dana Randall.